import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description: leetcode: 22. 括号生成
 * <a href="https://leetcode.cn/problems/generate-parentheses/">...</a>
 * User: DELL
 * Date: 2023-07-18
 * Time: 22:34
 */
public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        // 题目保证输入合法,因此不需要进行合法性检验
        StringBuffer temp = new StringBuffer();
        dfs(res,n,0,0,temp);
        return res;
    }

    /**
     * dfs 遍历所有情况
     * @param res   结果集
     * @param n     括号的组数
     * @param num1  当前左括号的数量
     * @param num2  左括号数 - 右括号数,即当前可插入的右括号数
     * @param temp  临时记录结果
     */
    private void dfs(List<String> res, int n, int num1, int num2, StringBuffer temp) {
        if (num1 == n && num2 == 0) {
            res.add(new String(temp));
        }
        if (num1 <= n) {
            temp.append('(');
            dfs(res,n,num1+1,num2+1,temp);
            temp.deleteCharAt(temp.length()-1);
        }
        if (num2 >= 1) {
            temp.append(')');
            dfs(res,n,num1,num2-1,temp);
            temp.deleteCharAt(temp.length()-1);
        }
    }
}